package ljl.codetop300;

public class _208_trie {

  /**
   * 居然过了，但是感觉写的很恶心
   */
  static class t {
    class Trie {

      Trie[] children = new Trie[26];
      boolean leaf;
      char c;
      public void insert(String word) {
        Trie node = this;
        for (int i = 0; i < word.length(); i++) {
          char c = word.charAt(i);
          Trie child = node.children[c - 'a'];
          if (child == null) {
            child = new Trie();
            child.c = c;
            node.children[c - 'a'] = child;
          }
          node = child;
        }
        node.leaf = true;
      }

      public boolean search(String word) {
        Trie node = this;
        for (int i = 0; i < word.length(); i++) {
          char c = word.charAt(i);
          Trie child = node.children[c - 'a'];
          if (child == null) return false;
          node = child;
        }
        return node.leaf;
      }

      public boolean startsWith(String prefix) {
        Trie node = this;
        for (int i = 0; i < prefix.length(); i++) {
          char c = prefix.charAt(i);
          Trie child = node.children[c - 'a'];
          if (child == null) return false;
          node = child;
        }
        return true;
      }
    }
  }

  /**
   * 感觉和我写的差不多
   */
  static class Trie {
    private Trie[] children;
    private boolean isEnd;

    public Trie() {
      children = new Trie[26];
      isEnd = false;
    }

    public void insert(String word) {
      Trie node = this;
      for (int i = 0; i < word.length(); i++) {
        char ch = word.charAt(i);
        int index = ch - 'a';
        if (node.children[index] == null) {
          node.children[index] = new Trie();
        }
        node = node.children[index];
      }
      node.isEnd = true;
    }

    public boolean search(String word) {
      Trie node = searchPrefix(word);
      return node != null && node.isEnd;
    }

    public boolean startsWith(String prefix) {
      return searchPrefix(prefix) != null;
    }

    private Trie searchPrefix(String prefix) {
      Trie node = this;
      for (int i = 0; i < prefix.length(); i++) {
        char ch = prefix.charAt(i);
        int index = ch - 'a';
        if (node.children[index] == null) {
          return null;
        }
        node = node.children[index];
      }
      return node;
    }
  }

  /**
   * 就这吧尽力了
   */
  static class tryagain {
    class Trie {
      Trie[] children = new Trie[26];
      boolean leaf;

      public void insert(String word) {
        Trie node = this;
        for (int i = 0; i < word.length(); i++) {
          int index = word.charAt(i) - 'a';
          Trie child = node.children[index];
          if (child == null) {
            child = new Trie();
            node.children[index] = child;
          }
          node = child;
        }
        node.leaf = true;
      }

      public boolean search(String word) {
        Trie node = tryFind(word);
        return node != null && node.leaf;
      }

      public boolean startsWith(String prefix) {
        return tryFind(prefix) != null;
      }

      Trie tryFind(String word) {
        Trie node = this;
        for (int i = 0; i < word.length(); i++) {
          int index = word.charAt(i) - 'a';
          Trie child = node.children[index];
          if (child == null) return null;
          node = child;
        }
        return node;
      }
    }
  }

}
